package com.company.test27_28;

import java.util.*;

/**
 * Created by Administrator on 2016.11.10.
 */
public class WeightedGraph<V> extends AbstractGraph<V>{

    private List<PriorityQueue<WeightedEdge>> queues;

    public WeightedGraph(int[][] edges,V[] vertices){
        super(edges,vertices);
        createQueues(edges,vertices.length);
    }

    public WeightedGraph(int[][] edges,int numberOfVertices){
        super(edges,numberOfVertices);
        createQueues(edges,numberOfVertices);
    }

    public WeightedGraph(List<WeightedEdge> edges,int numberOfVertices){
        super((List)edges,numberOfVertices);
        createQueues(edges,numberOfVertices);
    }

    public WeightedGraph(List<WeightedEdge> edges,V[] vertices){
        super((List)edges,vertices);
        createQueues(edges, vertices.length);
    }

    public WeightedGraph(int[][] edges,List<V> vertices){
        super(edges,vertices);
        createQueues(edges,vertices.size());
    }

    public WeightedGraph(List<WeightedEdge> edges,List<V> vertices){
        super((List) edges,vertices);
        createQueues(edges,vertices.size());
    }

    //打印所有的边
    public void printWeightedEdges() {
        for(int i=0;i<queues.size();i++){
            System.out.print("Vertex "+i+": ");
            for(WeightedEdge edge:queues.get(i)){
                System.out.printf("(%d,%d,%d) ",edge.getU(),edge.getV(),edge.getWeight());
            }
            System.out.println();
        }
    }

    //建立优先队列
    private void createQueues(int[][] edges,int numberOfVertices){
        queues=new ArrayList<>();
        for(int i=0;i<numberOfVertices;i++){
            queues.add(new PriorityQueue<>());
        }

        for(int i=0;i<edges.length;i++){
            int u=edges[i][0];
            int v=edges[i][1];
            int weight=edges[i][2];
            queues.get(u).offer(new WeightedEdge(u,v,weight));
        }
    }

    //建立优先队列
    private void createQueues(List<WeightedEdge> edges,int numberOfVertices){
        queues=new ArrayList<>();
        for(int i=0;i<numberOfVertices;i++){
            queues.add(new PriorityQueue<>());
        }

        for(WeightedEdge edge:edges){
            queues.get(edge.getU()).offer(edge);
        }
    }

    //以0为默认点返回一颗最小生成树
    public MST getMinimumSpanningTree(){
        return getMinimumSpanningTree(0);
    }

    //返回一颗最小生成树
    public MST getMinimumSpanningTree(int startingIndex){
        List<Integer> T=new ArrayList<>();
        T.add(startingIndex);

        List<PriorityQueue<WeightedEdge>> map=this.deepClone();

        PriorityQueue<WeightedEdge> queue=new PriorityQueue<>();
        queue.offer(map.get(startingIndex).poll());

        int totalWeight=0;

        int[] parent=new int[getSize()];
        for(int i=0;i<parent.length;i++){
            parent[i]=-1;
        }

        while (T.size()<getSize()&&!queue.isEmpty()){
            WeightedEdge edge=queue.poll();
            if(!map.get(edge.getU()).isEmpty()){
                queue.offer(map.get(edge.getU()).poll());
            }

            if(T.contains(edge.getV())){
                continue;
            }

            T.add(edge.getV());
            if(!map.get(edge.getV()).isEmpty()){
                queue.offer(map.get(edge.getV()).poll());
            }

            parent[edge.getV()]=edge.getU();
            totalWeight+=edge.getWeight();
        }
        return new MST(startingIndex,parent,T,totalWeight);
    }

    //复制queues
    private List<PriorityQueue<WeightedEdge>> deepClone(){
        List<PriorityQueue<WeightedEdge>> cloneQueues=new ArrayList<>();

        for(int i=0;i<this.queues.size();i++){
            cloneQueues.add(new PriorityQueue<>());
            for(WeightedEdge edge:this.queues.get(i)){
                cloneQueues.get(i).add(edge);
            }
        }
        return cloneQueues;
    }

    //最小生成树类
    public class MST extends SpanningTree{
        private int totalWight;

        public MST(int root,int[] parent,List<Integer> searchOrder,int totalWight){
            super(root,parent,searchOrder);
            this.totalWight=totalWight;
        }

        public int getTotalWight(){
            return totalWight;
        }
    }

    //返回一棵最小路径树，一般算法
    public ShortestPathTree getShortestPath(int sourceIndex){
        //算法搜索的路径
        List<Integer> T=new ArrayList<>();
        T.add(sourceIndex);

        int[] parent=new int[getSize()];
        parent[sourceIndex]=-1;

        int[] costs=new int[getSize()];
        for(int i=0;i<costs.length;i++){
            costs[i]=Integer.MAX_VALUE;
        }

        costs[sourceIndex]=0;

        List<PriorityQueue<WeightedEdge>> queues=this.deepClone();
        while (!queues.isEmpty()&&T.size()<getSize()){
            int minCost=Integer.MAX_VALUE;
            int v=-1;
            for(Integer u:T){
                while (!queues.get(u).isEmpty()&&T.contains(queues.get(u).peek().getV())){
                    queues.get(u).poll();
                }

                if(queues.get(u).isEmpty()){
                    continue;
                }

                if(queues.get(u).peek().weight+costs[u]<minCost){
                    minCost=queues.get(u).peek().weight+costs[u];
                    v=queues.get(u).peek().getV();
                    parent[v]=u;
                }
            }

            if(v!=-1){
                costs[v]=minCost;
                T.add(v);
            }
        }
        return new ShortestPathTree(sourceIndex,parent,T,costs);
    }

    //最短路径树，包括从单一源到其所有连通点的路径的集合
    public class ShortestPathTree extends SpanningTree{
        private int[] costs;//costs[v]代表的是其源root到v的最短路径

        public ShortestPathTree(int source,int[] parent,List<Integer> searchOrder,int[] costs){
            super(source,parent,searchOrder);
            this.costs=costs;
        }

        //返回相应源的最小权重值
        public int getCost(int v){
            return costs[v];
        }

        //打印所有源的最小权重
        public void printAllPaths(){
            System.out.println("All shortest paths form "+vertices.get(getRoot())+" are:");
            for(int i=0;i<costs.length;i++){
                printPath(i);
                System.out.println("(cost: "+costs[i]+")");
            }
        }
    }

    //有权边类
    public static class WeightedEdge extends Edge implements Comparable<WeightedEdge>{
        private int weight;

        public WeightedEdge(int u,int v,int weight){
            super(u,v);
            this.weight=weight;
        }

        public int getWeight(){
            return weight;
        }

        @Override
        public int compareTo(WeightedEdge o) {
            if(weight>o.weight){
                return 1;
            }else if(weight==o.weight){
                return 0;
            }else {
                return -1;
            }
        }
    }

    //返回最短的一条哈密尔顿环,若其不存在则返回一个大小为0的数组
    public List<Integer> getShortestHamiltonianCycle(int sourceIndex){
        List<Integer> cycle=new ArrayList<>();
        int minTotal=Integer.MAX_VALUE;
        getShortestHamiltonianCycle(sourceIndex,new ArrayList<>(),
                minTotal,cycle,new boolean[getSize()],0,sourceIndex);
        return cycle;
    }
    private int getShortestHamiltonianCycle(int u,List<Integer> integers,int minTotal,
                                             List<Integer> minCycle,boolean[] isVisited,
                                             int total,int start){
        isVisited[u]=true;
        integers.add(u);
        if(allVisited(isVisited)){
            for(WeightedEdge neighbor:queues.get(u)){
                if(neighbor.getV()==start){
                    if(total<minTotal){
                        minCycle.clear();
                        for(int i=0;i<integers.size();i++){
                            minCycle.add(integers.get(i));
                        }
                        minCycle.add(start);
                        minTotal=new Integer(minTotal);
                    }
                    break;
                }
            }
            isVisited[u]=false;
            integers.remove(integers.size()-1);
            return minTotal;
        }

        for(WeightedEdge edge:queues.get(u)){
            if(!isVisited[edge.getV()]&&start!=edge.getV()){
                minTotal=getShortestHamiltonianCycle(edge.getV(),integers,minTotal,
                        minCycle,isVisited,total+edge.getWeight(),start);
            }
        }
        isVisited[u]=false;
        integers.remove(integers.size()-1);
        return minTotal;
    }

    public static void main(String[] args) {
        String[] vertices={"Seattle","San Francisco","Los Angeles","Denver",
                "Kansas City","Chicago","Boston","NewYork","Atlanta","Miami",
                "Dallas","Houston"};

        int[][] edges={
                {0,1,807},{0,3,1331},{0,5,2097},{1,0,807},{1,2,381},{1,3,1267},
                {2,1,381},{2,3,1015},{2,4,1663},{2,10,1435},{3,0,1331},{3,1,1267},
                {3,2,1015},{3,4,599},{3,5,1003},{4,2,1663},{4,3,599},{4,5,533},{4,7,1260},
                {4,8,864},{4,10,496},{5,0,2097},{5,3,1003},{5,4,533},{5,6,983},{5,7,787},
                {6,5,983},{6,7,214},{7,4,1260},{7,5,787},{7,6,214},{7,8,888},{8,4,864},
                {8,7,888},{8,9,661},{8,10,781},{8,11,810},{9,8,661},{9,11,1187},
                {10,2,1435},{10,4,496},{10,8,781},{10,11,239},{11,8,810},{11,9,1187},
                {11,10,239}
        };

        WeightedGraph<String> graph1=new WeightedGraph<String>(edges,vertices);
        List<Integer> p=graph1.getHamiltonianPath(0);
        List<Integer> path=graph1.getShortestHamiltonianCycle(0);


        edges =new int[][]{
                {0,1,2},{0,3,8},{1,0,2},{1,2,7},{1,3,3},{2,1,7},
                {2,3,4},{2,4,5},{3,0,8},{3,1,3},{3,2,4},{3,4,6},
                {4,2,5},{4,3,6}
        };

        WeightedGraph<Integer> graph2=new WeightedGraph<Integer>(edges,5);
        //path=graph2.getShortestHamiltonianCycle(1);
        //tree2.printAllPaths();
        for(int i=0;i<path.size();i++){
            System.out.println(path.get(i));
        }
    }
}